Search results for "finite [mass]"
showing 10 items of 356 documents
Ultrametric Finite Automata and Turing Machines
2013
We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.
FINITE AUTOMATA WITH ADVICE TAPES
2014
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
Automata and forbidden words
1998
Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
Finite Automata with Advice Tapes
2013
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, and establish the relationships between this model and the previously studied ways of providing advice to finite automata.
Minimal forbidden words and factor automata
1998
International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.
Invariants of transverse foliations
2012
Abstract We construct two invariants for a pair of transverse one-dimensional foliations on the plane. If the set of separatrices is Hausdorff in the space of leaves, the invariant is a distinguished graph. In case there are a finite number of separatrices the invariant is an indexed link.
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
Almost square Banach spaces
2014
We single out and study a natural class of Banach spaces -- almost square Banach spaces. In an almost square space we can find, given a finite set $x_1,x_2,\ldots,x_N$ in the unit sphere, a unit vector $y$ such that $\|x_i-y\|$ is almost one. These spaces have duals that are octahedral and finite convex combinations of slices of the unit ball of an almost square space have diameter 2. We provide several examples and characterizations of almost square spaces. We prove that non-reflexive spaces which are M-ideals in their biduals are almost square. We show that every separable space containing a copy of $c_0$ can be renormed to be almost square. A local and a weak version of almost square spa…
Two-variable First-Order Logic with Counting in Forests
2018
We consider an extension of two-variable, first-order logic with counting quantifiers and arbitrarily many unary and binary predicates, in which one distinguished predicate is interpreted as the mother-daughter relation in an unranked forest. We show that both the finite satisfiability and the general satisfiability problems for the extended logic are decidable in NExpTime. We also show that the decision procedure for finite satisfiability can be extended to the logic where two distinguished predicates are interpreted as the mother-daughter relations in two independent forests.
Fundamentals on Decision-Making Behavior
2011
This introductory chapter describes the fundamentals for later analysis, modeling and discussion of choice tasks and behavior. Figure 2.1 depicts the basic elements of the choice process which are relevant for the present work. On the left hand side, we see the general problem the decision makers are faced with: the choice task. Generally speaking, a choice task defines the problem of choosing the preferred out of a discrete and finite set of alternatives. The decision makers’ preferences determine what the preferred alternative is. Thus, in Sect. 2.1, we define both choice tasks and preferences.